package org.datastructure.firstday.tree.threaded;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {

        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "Jode");
        HeroNode node6 = new HeroNode(14, "dim");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedTree();
        //   System.out.println(node5.getLeft());
        // System.out.println(node5.getRight());

        threadedBinaryTree.threadedList();
    }
}

class ThreadedBinaryTree {
    private HeroNode root;

    private HeroNode pre;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void threadedTree() {
        this.threadedTree(root);
    }


    public void threadedList() {

        HeroNode node = root;
        while (node != null) {

            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }

            System.out.println(node);
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }

            node = node.getRight();
        }


    }

    /**
     * 无论是前序、中序、后续都是从左至右遍历，因此是 left可能是子树，也可能是前驱节点
     * right 可能是子树，也可能是后继节点
     *
     * @param node
     */
    public void threadedTree(HeroNode node) {
        // TODO: 2022/1/3 heroNode left可能指向左子节点或者是前驱节点
        // TODO: 2022/1/3 right可能指向右子节点或者是后继节点

        if (node == null) {
            return;
        }

        threadedTree(node.getLeft());

        // TODO: 2022/1/3 主要内容都在这一步完成，有点难度
        // TODO: 2022/1/4 考虑到node.getLeft非空时，也就是指向子节点，为空时要指向前驱节点 
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }

        // TODO: 2022/1/3  右节点有子节点的不操作，为空的操作指向后继节点 
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;

        threadedTree(node.getRight());

    }
}
